// 视频链接 https://www.bilibili.com/video/BV1TK4y1h7S4?from=search&seid=16481976785205815304&spm_id_from=333.337.0.0
let arr = [49, 38, 65, 97, 76, 13, 69, 48];
arr.unshift('flag');
console.log(arr); // 预处理数组，使数组下标为1的元素对应根节点， i/2 -> 双亲  2i -> 左孩子, 2i+1 ->右孩子

function sift(arr, k, end) {
  let i = k;
  let j = 2 * i;
  while (j <= end) {
    if (j < end && arr[j] < arr[j + 1])
      // <end 防止j+1后越界，j左孩子，j+1右孩子，和值更大的孩子进行交换
      j++;
    if (arr[i] < arr[j]) [arr[i], arr[j]] = [arr[j], arr[i]]; // 交换
    i = j;
    j = 2 * i;
  }
  // console.log(arr);
}

// 初始化堆
function initHeap(arr) {
  let n = arr.length - 1;
  for (let k = n / 2; k >= 1; k--) {
    sift(arr, k, n);
  }
  return arr;
}

function heapSort(arr) {
  // 初始化堆
  let n = arr.length - 1;
  let res = [];
  for (let k = n / 2; k >= 1; k--) {
    sift(arr, k, n);
  }
  for (let k = 1; k < n; k++) { // 重建堆时 处理堆中第一个到第 n - k个元素，第 n - k + 1 是有序的（最大或最小的）
     
    [arr[1], arr[n - k + 1]] = [arr[n - k + 1], arr[1]]; // n - k + 1当前堆的最后一个元素（k不断增大）
    res.push(arr[n - k + 1]);
    sift(arr, 1, n - k); // 重建堆
  }
  return res;
}

console.log(heapSort(arr));
